/**
 * https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
 * 电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * @param digits 
 */
const letterCombinations = (digits: string): string[] => {
    const ans: string[] = []
    // 为空
    if (digits === '') return ans

    const len = digits.length;

    // 数字和字母映射
    const map: Record<string, string> = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz'
    } 

    const dfs = (level: number, str: string) => {
        if (level === len) { // 到了临界点
            ans.push(str)
            return;
        }   
        // 获取对应的字母组合
        const letters = map[digits[level]]
        const l = letters.length;
        for (let i = 0; i < l; i++) {
            // 处理下一层
            dfs(level + 1, str + letters[i])
        }

    }

    dfs(0, '')

    return ans
};

letterCombinations('2')